Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

For example,

Given

  1.          1
  2.         / \
  3.        2   5
  4.       / \   \
  5.      3   4   6

The flattened tree should look like:

  1.    1
  2.     \
  3.      2
  4.       \
  5.        3
  6.         \
  7.          4
  8.           \
  9.            5
  10.             \
  11.              6

Solution:

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. public class Solution {
  11.   public void flatten(TreeNode root) {
  12.     if (root == null)
  13.       return;
  15.     Stack<TreeNode> stack = new Stack<>();
  16.     stack.push(root);
  18.     TreeNode last = null;
  20.     while (!stack.isEmpty()) {
  21.       TreeNode curr = stack.pop();
  23.       if (last != null) {
  24.         last.left = null;
  25.         last.right = curr;
  26.       }
  28.       if (curr.right != null)
  29.         stack.push(curr.right);
  31.       if (curr.left != null)
  32.         stack.push(curr.left);
  34.       last = curr;
  35.     }
  36.   }
  37. }